package top.humbleyuan.leet;

import org.junit.Test;
import top.humbleyuan.leet.datastructure.tree.TreeNode;
import top.humbleyuan.leet.util.MyListHandle;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author HumbleYuan
 * @Date 2019/10/17 9:24
 * @Des 树
 */
public class Tree {
    /**
     * 验证是否是相同的树
     */
    @Test
    public void tree100() {
        TreeNode head1 = new TreeNode(2);
        head1.formTree();

        TreeNode head2 = new TreeNode(2);
        head2.formTree();

        System.out.println(isSameTree(head1, head2));
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }

        if(p == null || q == null) {
            return false;
        }

        if(p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }


    /**
     * 二叉树的中序遍历
     * 递归和迭代
     */
    @Test
    public void tree94() {
        TreeNode head1 = new TreeNode(2);
        head1.formTree();

        List<Integer> traverse = new ArrayList<>();

        //递归
        link94_2(head1,traverse);


        List<Integer> traverse2 = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode temp = head1;
        while (!stack.empty() || temp != null) {

            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }

            //左树为空
            temp = stack.pop();
            traverse2.add(temp.val);

            //然后到最底层的右树
            temp = temp.right;

        }

        System.out.println("递归" + MyListHandle.ListToString(traverse));
        System.out.println("递归" + MyListHandle.ListToString(traverse2));
    }

    //中序递归
    public void link94_2(TreeNode head,List<Integer> traverse) {
        if(head != null) {
            if(head.left != null)
                link94_2(head.left,traverse);
            traverse.add(head.val);
            if(head.right != null)
                link94_2(head.right,traverse);
        }
    }

    /**
     * 平衡二叉树
     * 利用DFS
     * 递归思想(逆序)：看似是比较根节点左右子树的高度，
     * 实则是自底向上，会先找到最底下的节点，比较其左右字数高度，依次往上
     */
    @Test
    public void link110() {
        TreeNode head = new TreeNode(2);
        head.formTree();

        System.out.println(getHeight(head) != -1);
    }

    public int getHeight(TreeNode treeNode) {
        if(treeNode == null) {
            return 0;
        }

        // 计算左子树
        int lDepth = getHeight(treeNode.left);
        // 左子树就不平衡则提前中断
        if(lDepth == -1) {
            return lDepth;
        }

        // 计算右子树
        int rDepth = getHeight(treeNode.right);
        // 右子树就不平衡则提前中断
        if(rDepth == -1) {
            return rDepth;
        }

        // max是因为比较高度差，比较的是左右子树最大高度的差
        return Math.abs(lDepth - rDepth) > 1 ? -1 : Math.max(lDepth, rDepth) + 1;

    }


    /**
     * 树高
     */
    @Test
    public void tree_104() {

        TreeNode head = new TreeNode(2);
        head.formTree();

        // 方法二，递归
        System.out.println(tree_104_2(head));

        //tree_104_1(head);

    }

    private void tree_104_1(TreeNode head) {
        if(head == null) {
            System.out.println(0);
        }
        // 借助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);

        int depth = 0;

        while (!queue.isEmpty()) {

            Queue<TreeNode> temp = new LinkedList<>();
            for (TreeNode t : queue) {
                if (t.left != null) {
                    temp.offer(t.left);
                }

                if(t.right != null) {
                    temp.offer(t.right);
                }
            }
            queue = temp;
            depth++;
        }
        System.out.println(depth);
    }

    public int tree_104_2(TreeNode t) {
        if(t == null) {
            return 0;
        }

        int leftDepth = tree_104_2(t.left);
        int rightDepth = tree_104_2(t.right);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 验证二叉搜索树
     */
    @Test
    public void tree_98() {
        TreeNode head = new TreeNode(2);
        head.formTree();

        // 有个上下限的问题：

        System.out.println(isValid(head, Long.MIN_VALUE, Long.MAX_VALUE));
    }

    public boolean isValid(TreeNode root, long min, long max) {
        if(root == null) {
            return true;
        }

        if(root.val <= min || root.val >= max) {
            return false;
        }

        // 每次更新上下界
        // 左子树上界更新，下界不更新；右子树相反
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }

    /**
     * 树的层次遍历
     * 非递归
     */
    @Test
    public void tree_102() {
        TreeNode head = new TreeNode(2);
        head.formTree();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);

        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> headList = new ArrayList<>();
        headList.add(head.val);

        res.add(headList);

        while(!queue.isEmpty()) {
//           TreeNode curNode = queue.poll();

           Queue<TreeNode> cur = new LinkedList<>();
           ArrayList<Integer> curList = new ArrayList<>();
           while(!queue.isEmpty()) {
                TreeNode curNode = queue.poll();

                if(curNode.left != null) {
                    cur.offer(curNode.left);
                    curList.add(curNode.left.val);
                }

                if(curNode.right != null) {
                    cur.offer(curNode.right);
                    curList.add(curNode.right.val);
                }
           }

           if(curList.size() > 0) {
               res.add(curList);
           }

           queue = cur;
        }

        System.out.println(res);
    }

    /**
     * 层次遍历
     * 递归
     */
    @Test
    public void leet_102_2() {
        TreeNode head = new TreeNode(2);
        head.formTree();

        List<List<Integer>> res = new ArrayList<>();
        recursion(head, 0, res);

        System.out.println(res);
    }

    public void recursion(TreeNode root, int level, List<List<Integer>> res) {
        if(root == null) {
            return;
        }

        if(level == res.size()) {
            res.add(new ArrayList<>());
        }

        res.get(level).add(root.val);

        recursion(root.left, level + 1, res);
        recursion(root.right, level + 1, res);
    }


    /**
     * 将树原地展开为链表
     */
    @Test
    public void leet_114() {
        TreeNode root = new TreeNode(2);
        root.formTree();

        flatten(root);

        System.out.println("asa");
    }

    public void flatten(TreeNode root) {
        if(root == null) {
            return;
        }

        if(root.left == null) {
            flatten(root.right);
        } else {
            if(root.right == null) {
                root.right = root.left;
            } else {
                // 将temp接到right的最右子树
                transfer(root.left, root.right);

                root.right = root.left;
            }

            flatten(root.right);

            // ** 注意要将左子树置为空
            root.left = null;
        }
    }

    public void transfer(TreeNode root, TreeNode temp) {

        while(root.right != null) {
            root = root.right;
        }

        root.right = temp;
    }
}
